package test.day06;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.function.Predicate;

public class MergeKLists {
	public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
	public ListNode mergeKLists(ListNode[] lists) {
		ListNode dummy = new ListNode(0);
		ListNode curr = dummy;
		// 使用优先队列
		PriorityQueue<ListNode> priorityQueue = new PriorityQueue() {
			@Override
			public Comparator comparator() {
				return new Comparator() {
					@Override
					public int compare(Object o1, Object o2) {
						return ((ListNode)o1).val - ((ListNode)o2).val;
					}
				};
			}
		};
		for (ListNode listNode : lists) {
			if (listNode != null) {
				priorityQueue.add(listNode);
			}
		}

		while (!priorityQueue.isEmpty()) {
			// 最小的出队
			ListNode node = priorityQueue.poll();
			if (node.next != null) {
				priorityQueue.add(node.next);
			}
			curr.next = node;
			curr = curr.next;
		}
		return dummy.next;
	}
}
